//给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。
// 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：3
// 
//
// 示例 2： 
//
// 
//输入：n = 11
//输出：0
//解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 2³¹ - 1 
// 
//
// Related Topics 数学 二分查找 👍 388 👎 0

package leetcode.editor.cn;
//java:第 N 位数字
public class Q0400NthDigit {
    public static void main(String[] args){
        Solution solution = new Q0400NthDigit().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findNthDigit(int n) {
        if (n < 1) return 0;
        int digit = 1; // 数字位数
        int start = 1; // digit位数字的开始数字
        int count = 9; // digit位数字的个数
        int num; // 转换出的数字
        int res;

        while (n > count) {
            n = n - count;
            digit++;
            start = start * 10;
            count = digit * start * 9;
        }
        num = start + (n - 1) / digit; // 转换出的数字
        res = Long.toString(num).charAt((n - 1) % digit) - '0'; // 转换出的数字的第几位数字是结果，转换成字符串格式
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}